/*
    f(n) = f(n-1) + f(n-2)
*/

#include <stdio.h>

#define FLOOR_FIRST 1
#define FLOOR_SECOND 2
#define FLOOR_THIRD 3

/* 1. 递推迭代+状态压压缩 */
static int jumpFloor(int n) {
    int pre = FLOOR_FIRST;
    int cur = FLOOR_SECOND;

    if (n == FLOOR_FIRST || n == FLOOR_SECOND) {
        return n;
    }

    for (int i = FLOOR_THIRD; i <= n; i++) {
        cur = pre + cur;
        pre = cur - pre;
    }
    return cur;
}


/* 2. 暴力递归 */
// 存在大量重复计算，比较耗时
// 由于是递归，比较消耗栈空间
int jumpFloor(int n) {
    if (n == 1 || n == 2)
        return n;
    return jumpFloor(n-2) + jumpFloor(n-1);
}

